/**********************************************************************
**	Authors: Erik Sapir & Lior Zivi

**
** Ordered set using coarse-grained synchronization.
** In this implementation, remove,add and contain operations 
** are blocking.
**
**
**********************************************************************/

#ifndef __COARSE_LIST__H
#define __COARSE_LIST__H


#include "framework/cpp_framework.h"
#include <memory>
#include "set.h"

using namespace CMDR;

template<typename T>
class CoarseList : public set<T> {

private:

	//list node
	class Node {
	public:

		const T				m_item; //the item stored 
		VolatileType<Node*>	m_next;  //next node in list

		//node contructors
		Node(const T& item) : m_item(item), m_next(null) { }
		Node(const T& item, Node* const next) : m_item(item), m_next(next) { }

		virtual ~Node() {;}
	};

private:
	CMDR::ReentrantLock m_lock; //synchronized access to list
	VolatileType<int>	m_size; //number of elements in list
	VolatileType<Node*>	m_head; //first list node

public:

	//constructor - builds new Coarse-Grained list
	CoarseList(int numOfThreads) :  m_size(0) {
		printf("\n\tSet Is: Coarse Grained List\n");

		// Add sentinels to start and end
		m_head = new Node(Integer::MIN_VALUE, null);
		Node* tail = new Node(Integer::MAX_VALUE);
		m_head->m_next = tail;
	}

	//desctructor - removes all list elements
	~CoarseList() {
		//we assume no one access the object at this point.
		Node* curr = m_head;
		Node* next = null;

		//go ovel all list elements and delete them
		while(null != curr) {
			next = curr->m_next;
			delete curr;
			curr = next;
		}
	}

	bool add(const T& item, int threadID) {
		Node* pred;
		Node* curr;

		bool returnValue;

		//lock the list
		m_lock.lock();
		
		try {
			pred = m_head;
			curr = pred->m_next;
		
			//search for the first element equal or larger to the new element
			while(curr->m_item < item){
				pred = curr;
				curr = curr->m_next;
			}
		
			if (curr->m_item == item){
				//element already exist in list - nothing to add
				returnValue = false;
			}
			else {
				//add the new element to the list
				std::auto_ptr<Node> node(new Node(item, curr));
				pred->m_next = node.get();

				node.release();

				//element added successfully - increment number of elements in list
				m_size++;

				returnValue = true;
			}
		}
		catch (const std::exception& ){
			returnValue = false;
		}

		//always unlock
		m_lock.unlock();

		return returnValue;
	}

	bool remove(const T& item, int threadID) {
		Node* pred;
		Node* curr;

		bool returnValue;

		//lock the list!	
		m_lock.lock();

		try {
			pred = m_head;
			curr = pred->m_next;

			//search for the first element equal or larger to the element to be removed
			while(curr->m_item < item){
				pred = curr;
				curr = curr->m_next;
			}

			if (curr->m_item == item){
				// remove the element from the list
				pred->m_next = curr->m_next;

				delete curr;

				//element removed successfully - decrement number of elements in list
				m_size--;

				returnValue = true;
			}
			else {
				//element was not found in the list - nothing to remove
				returnValue = false;
			}
		}
		catch (const std::exception& ){
			returnValue = false;
		}
			
		// always unlock
		m_lock.unlock();

		return returnValue;
	}

	bool contains(const T& item, int threadID) {
		Node* pred;
		Node* curr;
		
		//lock the list!	
		m_lock.lock();

		bool returnValue;

		try {
			pred = m_head;
			curr = pred->m_next;

			//search for the first element equal or larger to the element we are searching
			while(curr->m_item < item){
				pred = curr;
				curr = curr->m_next;
			}

			//return true iff found the element in the list
			if (curr->m_item == item){
				returnValue = true;	
			} else {
				returnValue = false;
			}
		}
		catch (const std::exception& ){
			returnValue = false;
		}

		//always unlock
		m_lock.unlock(); 

		return returnValue;
	}

	void clean(int threadID) {
		//lock the list - than remove all elements from list
		m_lock.lock(); 

		//crreate new tail, se head.next = newTails and
		//than delete all old elements
		Node* newTail = new Node(Integer::MAX_VALUE);
		Node* oldFirst = m_head->m_next;
		m_head->m_next = newTail;

		//no elements in the list now
		m_size = 0;

		Node* curr;
		Node* succ;
		curr = oldFirst;

		//go over the list and delete all elements
		do {
			succ = curr->m_next;
			delete curr;
			curr = succ;
		} while(null != curr);

		//always unlock
		m_lock.unlock();
	}

	bool isEmpty(int threadID) {
		//if no elements in list that size should be '0'
		return m_size == 0;
	}
	int size(int threadID){
		return m_size;
	}
};

#endif //__COARSE_LIST__H
